package org.ala.linshen.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：
 *
 * 必须选择 一种 冰激凌基料。
 * 可以添加 一种或多种 配料，也可以不添加任何配料。
 * 每种类型的配料 最多两份 。
 * 给你以下三个输入：
 *
 * baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
 * toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
 * target ，一个整数，表示你制作甜点的目标价格。
 * 你希望自己做的甜点总成本尽可能接近目标价格 target 。
 *
 * 返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。
 *
 *
 *
 * 示例 1：
 *
 * 输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
 * 输出：10
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：
 * - 选择 1 号基料：成本 7
 * - 选择 1 份 0 号配料：成本 1 x 3 = 3
 * - 选择 0 份 1 号配料：成本 0 x 4 = 0
 * 总成本：7 + 3 + 0 = 10 。
 * 示例 2：
 *
 * 输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
 * 输出：17
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：
 * - 选择 1 号基料：成本 3
 * - 选择 1 份 0 号配料：成本 1 x 4 = 4
 * - 选择 2 份 1 号配料：成本 2 x 5 = 10
 * - 选择 0 份 2 号配料：成本 0 x 100 = 0
 * 总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。
 * 示例 3：
 *
 * 输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
 * 输出：8
 * 解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。
 * 示例 4：
 *
 * 输入：baseCosts = [10], toppingCosts = [1], target = 1
 * 输出：10
 * 解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。
 *
 *
 * 提示：
 *
 * n == baseCosts.length
 * m == toppingCosts.length
 * 1 <= n, m <= 10
 * 1 <= baseCosts[i], toppingCosts[i] <= 104
 * 1 <= target <= 104
 *
 * @author ala
 * @date 2024-10-10 16:00
 */
public class Q1774 {

    public static void main(String[] args) {
        Q1774 q = new Q1774();

//        int[] baseCosts = {1, 7},
//              toppingCosts = {3, 4};
//        int target = 10;

//        int[] baseCosts = {2, 3},
//                toppingCosts = {4, 5, 100};
//        int target = 18;

//        int[] baseCosts = {3, 10},
//                toppingCosts = {2, 5};
//        int target = 9;

//        int[] baseCosts = {10},
//                toppingCosts = {1};
//        int target = 1;

        int[] baseCosts = {4},
                toppingCosts = {9};
        int target = 9;

        System.out.println(q.closestCost(baseCosts, toppingCosts, target));
    }

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
//        return V1(baseCosts, toppingCosts, target);
        return V2(baseCosts, toppingCosts, target);
    }
    /**
     *  回溯
     *  1）每种基座选择一次，遍历每个基座
     *  2）扩展配料表，每个配料多一份。新配料表每个配料就有选或不选两种状态，且新配料表长度最多为20
     *  3）在配料表上跑回溯，返回：基座 + 配料 最接近target的那个值
     */
    protected int V1(int[] baseCosts, int[] toppingCosts, int target) {
        //  扩展配料表
        int[] tcs = expandToppingCosts(toppingCosts);

        //  枚举每种基座，跑回溯
        int diff = Integer.MAX_VALUE, res = 0;
        for (int b : baseCosts) {
            tmp = 0; absTmp = Integer.MAX_VALUE;
            backTrick(0, tcs, 0, target - b);
            int r = b + tmp, d = Math.abs(r - target);

            if (d < diff) {
                diff = d;
                res = r;
            } else if (d == diff && r < res) {
                res = r;
            }
        }
        return res;
    }
    /**
     *  扩展配料表
     */
    protected int[] expandToppingCosts(int[] toppingCosts) {
        int tn = toppingCosts.length;
        int[] tcs = new int[tn << 1];
        for (int i = 0 ; i < tcs.length ; i++) {
            if (i < tn) {
                tcs[i] = toppingCosts[i];
            } else {
                tcs[i] = toppingCosts[i - tn];
            }
        }
        return tcs;
    }
    protected int tmp, absTmp;
    protected void backTrick(int i, int[] tcs, int crt, int target) {
        if (i == tcs.length) {
            int abst = Math.abs(target - crt);
            if (abst < absTmp) {
                absTmp = abst;
                tmp = crt;
            } else if (abst == absTmp && crt < tmp) {
                tmp = crt;
            }
            return;
        }

        //  选 或 不选
        backTrick(i + 1, tcs, crt + tcs[i], target);
        backTrick(i + 1, tcs, crt, target);
    }


    /**
     *  01bag
     *  1）如果最小的基座已经超过target，则最小基座就答案
     *      过程中如果某个基座正好等于target，那就他了
     *  2）否则超过target的基座可以不要，因为小于target的基座一个配料都不加也是允许的
     *      问题变为：在小于target的基座中，找到价格 <= target 的最大值
     *  3）dp[i][j] = 表示前i个配料，能否达到价格j。j的上限是target
     *  4）最后dp[n][j]为true的最大的j，和大于target的基座，取 | - target| 的最小值即可
     */
    protected int V2(int[] baseCosts, int[] toppingCosts, int target) {
        //  扩展配料表
        int[] tcs = expandToppingCosts(toppingCosts);

        //  挑出价格小于target的基座，该基座的价值是可以直接达到的
        List<Integer> bcs = new ArrayList<>();
        boolean[] dp = new boolean[target + 1];
        int minBase = Integer.MAX_VALUE;
        for (int b : baseCosts) {
            if (b < target) {
                bcs.add(b);
                dp[b] = true;
            } else if (b == target) {
                return b;
            } else {
                minBase = Math.min(minBase, b);
            }
        }

        for (int t : tcs) {
            for (int j = target ; j >= 0 ; j--) {
                if (dp[j] && j + t > target) {
                    minBase = Math.min(minBase, j + t);
                }
                if (j - t >= 0) {
                    dp[j] = dp[j] || dp[j - t];
                }
            }
        }
        for (int j = target ; j >= 0 ; j--) {
            if (dp[j]) {
                return (target - j) <= (minBase - target) ? j : minBase;
            }
        }

        return minBase;
    }


}
